﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace QuickHull
{
    public delegate void DrawFunction(List<Point> convexHull);

    class QuickHullAlgorithm
    {
        public DrawFunction draw { private get; set; }
        public bool drawIntermediateSteps { private get; set; }

        public List<Point> quickHull(List<Point> oripoints)
        {
            List<Point> points = new List<Point>(oripoints);
            List<Point> convexHull = new List<Point>();
            if(points.Count < 3) {
                return new List<Point>(points);
            }

            int minPoint = -1, maxPoint = -1;
            int minX = Int32.MaxValue;
            int maxX = Int32.MinValue;
            for(int i = 0; i < points.Count; i++)
            {
                if (points[i].X < minX)
                {
                    minX = points[i].X;
                    minPoint = i;
                }
                if (points[i].X > maxX)
                {
                    maxX = points[i].X;
                    maxPoint = i;
                }
            }

            Point A = points[minPoint];
            Point B = points[maxPoint];
            convexHull.Add(A);
            convexHull.Add(B);
            points.Remove(A);
            points.Remove(B);

            List<Point> leftSet  = new List<Point>();
            List<Point> rightSet = new List<Point>();

            for(int i = 0; i < points.Count; i++)
            {
                Point p = points[i];
                if(pointLocation(A, B, p) == -1) {
                    leftSet.Add(p);
                }
                else { 
                    rightSet.Add(p);
                }
            }
            if(drawIntermediateSteps) {
                draw(convexHull);
            }
            hullSet(A, B, rightSet, convexHull);
            if(drawIntermediateSteps) {
                draw(convexHull);

            }
            hullSet(B, A, leftSet, convexHull);

            return convexHull;
        }

        public int calcDistance(Point A, Point B, Point C)
        {
            int ABx = B.X - A.X;
            int ABy = B.Y - A.Y;
            int num = ABx * (A.Y - C.Y) - ABy * (A.X - C.X);
            if (num < 0) {
                num = -num;
            }
            return num;
        }

        public void hullSet(Point A, Point B, List<Point> set, List<Point> hull)
        {
            int insertPosition = hull.IndexOf(B);
            if(set.Count == 0) {
                return;
            }
            if (set.Count == 1)
            {
                Point p = set[0];
                set.Remove(p);
                hull.Insert(insertPosition, p);
                return;
            }

            int dist = Int32.MinValue;
            int furthestPoint = -1;
            for (int i = 0; i < set.Count; i++)
            {
                Point p = set[i];
                int distance = calcDistance(A, B, p);
                if (distance > dist)
                {
                    dist = distance;
                    furthestPoint = i;
                }
            }
            Point P = set[furthestPoint];
            set.RemoveAt(furthestPoint);
            hull.Insert(insertPosition, P);

            // Determine who's to the left of AP
            List<Point> leftSetAP = new List<Point>();
            for(int i = 0; i < set.Count; i++)
            {
                Point M = set[i];
                if(pointLocation(A, P, M) == 1) {
                    leftSetAP.Add(M);
                }
            }

            // Determine who's to the left of PB
            List<Point> leftSetPB = new List<Point>();
            for(int i = 0; i < set.Count; i++)
            {
                Point M = set[i];
                if(pointLocation(P, B, M) == 1) {
                    leftSetPB.Add(M);
                }
            }

            if(drawIntermediateSteps) {
                draw(hull);
            }
            hullSet(A, P, leftSetAP, hull);
            if(drawIntermediateSteps) {
                draw(hull);
            }
            hullSet(P, B, leftSetPB, hull);
            if(drawIntermediateSteps) {
                draw(hull);
            }
        }

        public int pointLocation(Point A, Point B, Point P)
        {
            int cp1 = (B.X - A.X) * (P.Y - A.Y) - (B.Y - A.Y) * (P.X - A.X);
            return (cp1 > 0) ? 1 : -1;
        }
    }
}
